/*!\file GRAPH.hpp
 * \author Christopher Crance, Westin Sykes
 * \brief class implementation for an undirected graph
 */
/*
template <class T, unsigned int N>
GRAPH<T,N>::GRAPH()
{
  
  COLLECTION<T>::m_size=N;
  DIRECTED_GRAPH<T,N>::m_vData = new T[N];  //allocate vertices array for N vertices
  for(int i = 0; i < N; i++)  //set all elements of vert array to default value for type T
    DIRECTED_GRAPH<T,N>::m_vData[i] = T();
  
  DIRECTED_GRAPH<T,N>::m_adjMatrix = new int*[N];  //allocate first dimension of adjacency matrix for N vertices
  for(int i = 0; i < N; i++)  //allocate second dimension of adj Matrix for N vertices
    DIRECTED_GRAPH<T,N>::m_adjMatrix[i] = new int[N];
  
  for(int i = 0; i < N; i++)  //set all elements of adjMatrix to 0 (no edges)
  {
    for(int j = 0; j < N; j++)
      DIRECTED_GRAPH<T,N>::m_adjMatrix[i][j] = 0;
  }
 
}
 */
template <class T, unsigned int N>
bool GRAPH<T,N>::isSimple() const
{
  //check for points connected to themselves
  for(int i=0; i<N; i++)
  {
    if(DIRECTED_GRAPH<T,N>::m_adjMatrix[i][i] != 0)
      return false;
  }
  return true;
}

template <class T, unsigned int N>
bool GRAPH<T,N>::isComplete() const
{
  if(N == 0)
    return true;
  if(!isSimple())
    return false;
  
  //calculate how many lines there should be in order to be complete assuming it is simple
  int numb = N-1;
  for(int i = N-2; i > 0; i--)
  {
    numb+=i;
  }
  
  //count how many lines there are in the graph
  int actualCount = 0;
  for(int i = 0; i < N; i++)
  {
    for(int j = 0; j < N; j++)
    {
       if(DIRECTED_GRAPH<T,N>::m_adjMatrix[i][j] != 0)
       {
         actualCount++;
       }
    }
  }
  actualCount = actualCount/2;  //divide by 2 b/c each edge is parallel
  return  actualCount==numb;
}

template <class T, unsigned int N>
bool GRAPH<T,N>::isAcyclic() const  
{
  //check for points connected to themselves
  for(int i=0; i<N; i++)
  {
    if(DIRECTED_GRAPH<T,N>::m_adjMatrix[i][i] != 0)
      return false;
  }
  
  //then check for other loops
  int foundArray[N];

  for(int i=0; i<N; i++)
  {
    for(int i=0; i<N; i++)
      foundArray[i] = NYV;
    if(loopFinder(0, foundArray))
      return false;
  }
  return true;
}

template <class T, unsigned int N>
bool GRAPH<T,N>::loopFinder(const int currentPos, int foundArray[], int previousPos) const
{
  bool loopFound=false;
  for(int i=0; i<N; i++)
  {
    if(currentPos==foundArray[i])
      loopFound=true;
  }
  if(loopFound && previousPos != -1)
  {
    return true;
  }
  for(int j=0; j<N; j++)
  {
    if(isEdge(currentPos,j) && j != previousPos)
    {
      //add the number of the visited node to the array
      for(int k = 0; k < N; k++)
      {
        if(foundArray[k] == NYV)
        {
          foundArray[k]=currentPos;
          previousPos = currentPos;
          break;
        }
      }
      if(loopFinder(j, foundArray, previousPos))
      {
        return true;
      }
    }
  }
  return false;
}

